package leetcode.code0741;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int m, n;

	int[][] grid;

	public int cherryPickup(int[][] grid) {
		m = grid.length;
		n = grid[0].length;
		this.grid = grid;
		Integer[][][][] dp = new Integer[m][n][m][n];
		int ans = this.cherryPickup(0, 0, 0, 0, dp);
		return ans == -1 ? 0 : ans;
	}

	private int cherryPickup(int a, int b, int c, int d, Integer[][][][] dp) {
		if (a == m || b == n || c == m || d == n) {
			return -1;
		}
		if (a == m - 1 && b == n - 1) {
			return this.grid[a][b];
		}
		if (this.grid[a][b] == -1 || this.grid[c][d] == -1) {
			return -1;
		}
		if (dp[a][b][c][d] != null) {
			return dp[a][b][c][d];
		}
		int ans = 0;
		if (a == c && b == d) {
			ans = this.grid[a][b];
		} else {
			ans = this.grid[a][b] + this.grid[c][d];
		}
		int best = -1;
		int ans1 = this.cherryPickup(a + 1, b, c + 1, d, dp);
		int ans2 = this.cherryPickup(a, b + 1, c, d + 1, dp);
		int ans3 = this.cherryPickup(a + 1, b, c, d + 1, dp);
		int ans4 = this.cherryPickup(a, b + 1, c + 1, d, dp);
		if (ans1 != -1) {
			best = ans1;
		}
		if (ans2 != -1) {
			best = Math.max(best, ans2);
		}
		if (ans3 != -1) {
			best = Math.max(best, ans3);
		}
		if (ans4 != -1) {
			best = Math.max(best, ans4);
		}
		if (best == -1) {
			ans = best;
		} else {
			ans += best;
		}
		dp[a][b][c][d] = ans;
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(0, this.cherryPickup(H.str2array1("[[1,1,-1],[1,-1,1],[-1,1,1]]")));
		H.compare(5, this.cherryPickup(H.str2array1("[[0,1,-1],[1,0,-1],[1,1,1]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
